﻿#include <iostream>

using namespace std;

void printfArray(int *array, int length) {
    for (int i = 0; i < length; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}

void adjustHeap(int *array, int i, int length) {
    while (i * 2 + 1 < length) {
        int k = i * 2 + 1;
        if (k + 1 < length && array[k] < array[k + 1]) {
            k++;
        }

        if (array[i] < array[k]) {
            int temp = array[i];
            array[i] = array[k];
            array[k] = temp;

            i = k;

        } else {
            break;
        }
    }
}

// 不稳定排序
void heapSort(int *array, int length) {
    // 构建最大堆
    for (int i = length / 2 - 1; i >= 0; i--) {
        adjustHeap(array, i, length);
    }

    for (int i = length - 1; i > 0; i--) {
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;

        adjustHeap(array, 0, i);
    }
}

int main() {
    int array[] = {2, 4, 6, 7, 3, 2, 5, 6, 7, 2, 2, 4, 2, 1, 4, 1, 6, 7, 9, 0, 8};
    int length = (sizeof(array) / sizeof(int));
    cout << "length = " << length << endl;

    cout << "排序前: ";
    printfArray(array, length);

    heapSort(array, length);

    cout << "排序后: ";
    printfArray(array, length);

    return 0;
}
